package src.skill_problem;

import java.util.HashMap;

public class no136 {  //只出现一次的数字
    public static void main(String[] args) {
        int[] arr={4,1,2,1,2};
        System.out.println(singleNumber2(arr));
    }

    // 异或运算，同0异1。因此：出现两次的数异或后为 0，0 异或 一个数 == 本身
    public static int singleNumber(int[] nums) {
        // 遍历数组，对数组元素逐个异或
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

    /**
     *  7种位运算：
     *  1、与 AND &
     *      任何数和0做与运算，结果是0
     *      任何数和自身做与运算，结果是自身
     *
     *  2、或 OR |
     *  任何数和0做或运算，结果是自身
     *  任何数和其自身做或运算，结果是自身
     *
     *  3、非 NOT !
     *
     *  4、异或 XOR ^=
     *      任何数和0做异或运算，结果是自身
     *      任何数和其自身做异或运算，结果是0
     *      异或运算满足交换律和结合律
     *
     *  5、左移 SHL <<
     *      左移n位等于乘以2的n次方
     *
     *  6、逻辑右移 SHR >>
     *      右移n位等于除以2的n次方
     *      逻辑右移运算会用0填充移位后产生的空位
     *
     *  7、算数右移 SAR >>>
     *      算术右移运算会用符号位填充移位后产生的空位
     */

    public static int singleNumber2(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num, 2);
            }else {
                map.put(num,1);
            }
        }
        for(int num : map.keySet()){
            if(map.get(num)==1){
                return num;
            }
        }
        return 0;
    }

}
